1. Field of the Invention
This invention relates generally to queuing techniques. More particularly, it relates to an efficient and reliable technique and apparatus for queuing high priority data for processing (e.g., for transmission) without risk of high latency due to prior queued lower priority data.
2. Background of Related Art
Queues are generally used by communications systems as a sort of holding bin for data packets after they are prepared for transmission, but before they are actually processed for transmission.
For instance, FIG. 6 shows the relevant portion of an exemplary transmission system including one or more software queues 120-124 containing data packets for transmission.
In particular, as shown in FIG. 6, the software queues 120-124 contain data of varying degrees of priority for transmission. For instance, data packets corresponding to a lower priority data transmission may relate, e.g., to the uploading of a web page, while a higher priority data transmission may relate, e.g., to a video or audio transmission. The particular priority levels assigned to various data packets may be determined by the particular application.
A priority queuing scheme 610 typically includes the relevant algorithms and/or arbitration rules to determine a fair ordering of data packets for transmission by the transmission system in a hardware portion of the transmission system. Generally speaking, a higher priority data packet will typically be pulled from the high priority queue 124 more frequently than will be lower priority data packets from a lower priority queue 120, so as to conform to desired latency requirements. Latency requirements relate to the maximum delays which will be incurred by any particular data packet, e.g., from the time it is placed on the relevant software queue 120-124 until the time that it finally gets pulled from a hardware queue 650 for appropriate encoding and transmission, e.g., by an RF front end.
A typical priority queuing routine in the priority queue module 610 will look at the contents of the various software priority queues 120-124, and determine which packet should be next added to the hardware transmit queue 650. Typical priority queuing routine considers, e.g., which packets are available, fairness, priority, throughput, transmit latency, and many other factors when deciding which data packet should be queued next into the hardware queue 650.
However, most priority queuing schemes do not work well when higher priority queues are temporarily empty. For instance, if there are only low priority packets available in the lowest priority queue 120 and no data packets available in the highest priority queue 124, then the priority queuing routine in the priority queue module 610 will fill the hardware transmit queue 650 with only low priority data. This may occur over a period of time, filling up the hardware queue 650 with only low priority packets, which must be cleared (i.e., transmitted) before the hardware queue 650 can accept any additional data packets for transmission. Although it is usually desirable to keep the hardware queue 650 as full as possible to optimize throughput, once a higher priority packet finally becomes available, the high priority packet will be placed onto the end of the hardware transmit queue 650, and may even have to wait for placement on the hardware queue 650, causing significant latency delays.
The typical conventional hardware transmit queue cannot easily be reordered, e.g., by software. This is because software reordering might create a race condition between the hardware and the software accessing the same hardware transmit queue 650. Moreover, hardware reordering of a hardware transmit queue 650 would be costly to implement, and/or result in a slower operation of the hardware transmit queue 650. Thus, the higher priority data packet, once reappearing in the higher priority software queue 124, will be forced to experience a significant latency. This significant latency would include time it would take to transmit all low priority packets already in the hardware transmit queue 650 at the time that the higher priority data packet gets queued into the hardware transmit queue 650. Moreover, in such situations, the significant latency time for the higher priority data packet may risk violation of latency constraints on the higher priority data packet.
The hardware transmit queue 650 could be made statically smaller to shorten the latency time through the hardware transmit queue 650, but this would tend to decrease the throughput of the transmission system.
Accordingly, there is a need for an efficient and reliable queuing technique and apparatus which provides sufficient and reliable servicing of high priority data at all times without necessarily causing a sacrifice in throughput.
In accordance with the principles of the present invention, a data packet queue comprises a priority queuing module adapted to submit to a data queue data packets in accordance with a priority of the data packets. A priority history module is adapted to monitor a history of priority levels of data packets submitted to the data queue. A depth of the hardware data queue is adaptively limited based on the monitored history of the priority levels of data packets.
A method of balancing latency with throughput in a data packet queue in accordance with another aspect of the present invention comprises determining a priority level history with respect to past submissions to the data packet queue. A depth of the data packet queue is adaptively adjusted based on the determined priority level history.